#define SIZE 100
#define LEFT 0
#define RIGHT 1


#include<stdio.h>
#include<stdlib.h>

typedef struct listNode  {
	int data;
	struct listNode* next;
} ListNode;

typedef struct list  {
	ListNode* head;
	ListNode* tail;
} List;

typedef struct treeNode
{
	unsigned int data;
	struct treeNode *parent;
	struct treeNode *left;
	struct treeNode *right;
}TreeNode;

typedef struct tree
{
	TreeNode *root;
	List leafList;
}Tree;


TreeNode *nodeFromArray(int *arr, int  size)
{
	TreeNode *ret;
	if(arr[size/2] == -1) return NULL;
	ret = malloc(sizeof(TreeNode));
	if(size==1)
	{
		if(arr[0]==-1) return NULL;
		ret->left = NULL;
		ret->right = NULL;
		ret->data = arr[0];
		return ret;
	}
	ret->data = arr[size/2];
	ret->left = nodeFromArray(arr, size/2);
	if(ret->left) ret->left->parent = ret;
	ret->right = nodeFromArray(arr + size/2 + 1, size/2);
	if(ret->right) ret->right->parent = ret;
	return ret;

}

Tree BuildTreeFromArray(int *arr, int  size)
{
	Tree ret;
	ret.root = nodeFromArray(arr, size);
	return ret;
}

ListNode *BuildLeafNode(TreeNode *n)
{
	ListNode *ret;
	ListNode *p;
	ret = NULL;
	if(!n) return NULL;
	if((!n->left)&&(!n->right))
	{
		ret = malloc(sizeof(ListNode));
		//printf("Adding %d\n", n->data);
		ret->data = n->data;
		return ret;
	}
	if(n->left) ret = BuildLeafNode(n->left);
	if((n->right)&&ret)
	{
		p = ret;
		while(p->next) p = p->next;
		p->next = BuildLeafNode(n->right);
	}
	else if(n->right) ret = BuildLeafNode(n->right);
	return ret;

}

List BuildLeafList(TreeNode *n)
{
	List ret;
	ListNode *p;
	ret.head = BuildLeafNode(n);
	p = ret.head;
	while(p->next) p=p->next;
	ret.tail = p;
	return ret;
}

Tree BuildTreeFromArrayWithLeafList(int *arr, int size)
{
	Tree ret;
	ret.root = nodeFromArray(arr, size);
	ret.leafList = BuildLeafList(ret.root);
	return ret;
}

void printNode(TreeNode *n)
{
	if(!n) return;
	printNode(n->left);
	printf("%d ",n->data);
	printNode(n->right);
}

void printTreeInorder(Tree tr)
{
	printNode(tr.root);
	printf("\n");
}
void freeNode(TreeNode *n)
{
	TreeNode *templ,*tempr;
	if(!n) return;
	templ = n->left;
	tempr = n->right;
	free(n);
	free(templ);
	free(tempr);
}

TreeNode *findParentNode(TreeNode *n, int data, int branchSelect)
{
	TreeNode *ret;
	if(!n) return NULL;
	if(n->data == data)
	{
		if((branchSelect == LEFT)&&!(n->left)) return n;
		if((branchSelect == RIGHT)&&!(n->right)) return n;

	}

	ret = findParentNode(n->left, data, branchSelect);
	if(ret) return ret;
	ret = findParentNode(n->right, data, branchSelect);
	return ret;
}

TreeNode *findParent(Tree tr, int data, int branchSelect)
{
	return findParentNode(tr.root, data, branchSelect);

}

Tree AddLeaf(Tree tr, TreeNode *n, int branchSelect, int data)
{
	TreeNode *p;
	p = malloc(sizeof(TreeNode));
	p->data = data;
	p->left = NULL;
	p->right = NULL;
	p->parent = n;
	if(branchSelect == LEFT) n->left = p;
	else if(branchSelect == RIGHT) n->right = p;
	//freeList(tr.leafList);
	tr.leafList = BuildLeafList(tr.root);
	return tr;

}

void printLeafList(Tree tr)
{
	ListNode *p;
	p = tr.leafList.head;
	while(p)
	{
		printf("%d ",p->data);
		p = p->next;
	}
	printf("\n");
}

void freeTree(Tree tr)
{
	freeNode(tr.root);
}

int main()
{

    int size, i;

    int arr[SIZE];

    Tree tr;

    TreeNode * p;

    int parentData, data, branchSelect;

    scanf("%d", &size);

    for(i=0; i<size; i++)

        scanf("%d", &arr[i]);

    scanf("%d%d%d", &parentData, &data, &branchSelect);

    tr = BuildTreeFromArrayWithLeafList(arr, size);//the array is given as described in question 1

    //scan the tree inorder (LDR) and find the first parent (a node with parentData as data) that has no child in branchSelect

    p = findParent(tr, parentData, branchSelect);

    tr = AddLeaf(tr, p, branchSelect, data);

    printTreeInorder(tr); //Print the tree in-order (LDR)

    printLeafList(tr); //Print the leaves from left to right

    freeTree(tr);

}
